#include <iostream>
using namespace std;
#define MVNum 100
typedef char VerTexType;//顶点数据类型设置为字符
typedef int ArcType;//边的权值为整型
typedef int OtherInfo;

/*********邻接矩阵***********/
struct AMGraph {
	VerTexType vexs[MVNum];//顶点表
	ArcType arcs[MVNum][MVNum];//邻接矩阵
	int vexnum;//顶点数量
	int	arcnum;//边数量
};


int Locatevex(AMGraph G, VerTexType v)//定位顶点下标
{
	for (int i = 0; i < G.vexnum; i++)//遍历寻找对应顶点下标
	{
		if (G.vexs[i]==v)
		{
			return i;
		}
	}
	return -1;
}
void CreateUDN(AMGraph&G, int vex_num, int edge_num)
{
	G.vexnum = vex_num;
    G.arcnum = edge_num;
	cout << "请输入各顶点信息：" << endl;
	for (int i = 0; i < G.vexnum; i++)//请输入各顶点信息
	{
		cin >> G.vexs[i];
	}
	for (int i = 0; i < G.vexnum; i++)//将邻接矩阵初始化为0
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0;
		}
	}
	for (int k = 0; k < G.arcnum; k++)
	{
		VerTexType v1, v2;
		int w;
		cout << "请依次输第入"<<k+1<<"条边的两个顶点及权值：";
		cin >> v1 >> v2 >> w;
		int i = Locatevex(G, v1);//找到顶点在图中边的下标
		int j = Locatevex(G, v2);
		if (i != -1 && j != -1)//如果能找到对应顶点，对边赋权值
		{
			G.arcs[i][j] = w;
		}
        else
        {
            cout << "顶点输入错误，请重新检查!" << endl;//顶点输入错误处理
            k-=1;
        }
	}
}
void listVertexes(AMGraph &g)
{
    for (int i = 0; i < g.vexnum; i++)//输出邻接表
    {
        cout << "第" << i + 1 << "个顶点：" << g.vexs[i] << endl;
    }
}

void listEdges(AMGraph &g)
{
    int k = 1;
    for (int i = 0; i < g.vexnum; i++)//输出邻接矩阵
    {	
        for (int j = 0; j < g.vexnum; j++)
        {
            if (g.arcs[i][j] != 0)
            {
                cout << "第" << k << "条边" << ": (" << g.vexs[i] << "," << g.vexs[j] << "," << g.arcs[i][j] << ")"  << endl;
                k++;
            }
        }
    }
}

/*********邻接表***********/

struct ArcNode {
	int adjvex;//连接的顶点下标
	struct ArcNode *nextarc;//下一节点
	OtherInfo info;//权值
};
struct VNode{
	VerTexType data;//顶点数据
	ArcNode *firstarc;//边的连接点
};
struct ALGraph{
	int vexnum;//顶点总数
	int arcnum;//边总数
    VNode vertices[MVNum];//顶点数组
};


int Locatevex(ALGraph G, VerTexType v)//定位顶点下标
{
	for (int i = 0; i < G.vexnum; i++)//遍历寻找对应顶点下标
	{
		if (G.vertices[i].data == v)
		{
			return i;
		}
	}
	return -1;
}
void CreateUDG(ALGraph &G, int vex_num, int edge_num)
{
    G.vexnum = vex_num;
    G.arcnum = edge_num;
	cout << "请输入各顶点信息：" << endl;
	for (int i = 0; i < G.vexnum; i++)//请输入各顶点信息
	{
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	for (int k = 0; k < G.arcnum; k++)
	{
		VerTexType v1, v2;
		int w;
		cout << "请依次输入" << k << "条边的两个顶点及权值：";
		cin >> v1 >> v2 >> w;
		int i = Locatevex(G, v1);//找到顶点在图中边的下标
		int j = Locatevex(G, v2);
        if (i != -1 && j != -1)//如果能找到对应顶点，对边赋权值
        {
            /*ArcNode *p1 =new ArcNode;//边用前插法插入到顶点后方
            p1->info = w;
            p1->adjvex = i;
            p1->nextarc = G.vertices[j].firstarc;
            G.vertices[j].firstarc= p1;*/
            ArcNode *p2 = new ArcNode;
            p2->info = w;
            p2->adjvex = j;
            p2->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p2;
        }
        else
        {
            cout << "顶点输入错误，请重新检查!" << endl;//顶点输入错误处理
        } 	
	}
}

void listVertexes(ALGraph &g)
{
    for (int i = 0; i < g.vexnum; i++)//输出邻接表
    {
        cout << "第" << i + 1 << "个顶点：" << g.vertices[i].data << endl;
    }
}

void listEdges(ALGraph &g)
{
    for (int i = 0; i < g.vexnum; i++)//输出邻接表
    {
        int k = 1;
        ArcNode *p = g.vertices[i].firstarc;
        while (p)
        {
            cout << "第" << k << "条边" << ": (" << g.vertices[i].data << "," << g.vertices[p->adjvex].data << "," <<  p->info << ")"  << endl;
            p = p->nextarc;
            k++;
        }
        }
}